package 复杂链表的复刻;

//import java.util.HashMap;
//
///**
// * Definition for singly-linked list with a random pointer.
// * class ListNode {
// * int val;
// * ListNode next, random;
// * ListNode(int x) { this.val = x; }
// * };
// */
//class Solution {
//    public ListNode copyRandomList(ListNode head) {
//        if (head == null) {
//            return head;
//        }
//        HashMap<ListNode, ListNode> map = new HashMap<ListNode, ListNode>();
//        for (ListNode p = head; p != null; p = p.next) {
//            map.put(p, new ListNode(p.val));
//        }
//        map.put(null, null);
//        for (ListNode p = head; p != null; p = p.next) {
//            map.get(p).next = map.get(p.next);
//            map.get(p).random = map.get(p.random);
//        }
//        return map.get(head);
//    }
//}
//
class ListNode {
    int val;
    ListNode next, random;

    ListNode(int x) {
        this.val = x;
    }
}

/**
 * Definition for singly-linked list with a random pointer.
 * class ListNode {
 * int val;
 * ListNode next, random;
 * ListNode(int x) { this.val = x; }
 * };
 */
class Solution {
    public ListNode copyRandomList(ListNode head) {
        if (head == null || head.next == null) return head;

        // 在每个点后面添加一个它的复制节点
        for (ListNode p = head; p != null; p = p.next.next) {
            ListNode clone = new ListNode(p.val);
            clone.next = p.next;
            p.next = clone;
        }

        // 复制random指针
        for (ListNode p = head; p != null; p = p.next.next) {
            if (p.random == null) continue;
            p.next.random = p.random.next;
        }
        // 分离两个链表
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        for (ListNode p = head; p != null; p = p.next) {
            tail.next = p.next;
            tail = tail.next;
            p.next = tail.next;
        }
        return dummy.next;
    }
}
